Large data processing machines normally have more than one storage facility. Usually these include a fast access buffer storage unit and an large capacity main storage unit. The fast access buffer is used to increase the apparent access time to data stored in the machine. The buffer operates by retrieving blocks of data from the main storage unit and holding the data ready for access by the central processing unit of the machine. The machine accesses the data from the buffer which in turn updates the data stored in the buffer from the main storage unit in an effort to keep currently active data in the buffer.
In addition to having more than one storage facility in a data processing machine, often the machine will use more than one addressing schemes for accessing the data in the storage facilities. There is always the system address which uniquely locates a given set of data within the main storage facility of the data processing machine. In addition, there may also be other non-unique addressing schemes, referred to as virtual addresses, which are assigned to a given CPU within the machine or a given programmer. The virtual addresses can be used to increase the apparent allocated storage space to a given user by disassociating the user to a certain degree from the system address. In this manner a given user may be actually allocated only a part of the system main storage facility while having at its disposal for programming a much larger set of virtual addresses. In this type of addressing scheme, of course, more than one virtual address may actually access the same set of data within the mainstore. That is, more than one virtual address may translate into the same system address.
Data processing machines which use virtual address-to-system address addressing schemes normally include a translation mechanism which stores tables that are accessible by the virtual address, or some function thereof, which keep information necessary to translate the virtual address to the system address. In this manner, the main storage facility which is accessed only by the system address can be accessed by the programmer using the virtual address.
Because a given system address may be the translation of more than one virtual address, the need may arise for computing all the virtual addresses which map to the given system address. For instance, in a data processing machine which allows direct access to the fast access buffer using the virtual address, such as is described in U.S. Pat. No. 4,612,612, Ser. No. 527,678, filed Aug. 30, 1983 entitled "VIRTUALLY ADDRESSED CACHE", (invented by Gene Myron Amdahl, Donald Laverne Hanson, and Gary Arthur Woffinden, filed contemporaneously herewith and owned by a common assignee), there is a need for a mechanism for translating the system address to all the synonym virtual addresses which map to that given system address. This need arises because data within the fast access buffer may be operated upon or changed in some manner at one virtual address location without directly making the same changes in all the synonym virtual addresses. So the translation from system address to all synonym virtual addresses must be performed in order to assure that data contained in the fast access buffer and all the synonym virtual address locations is accurate.
As described in more detail below in the detailed description of the preferred embodiment of the present invention, the translation from the system address to all system virtual addresses involve a search of a table storage unit which contains the information system necessary to complete the translation from the virtual address to the system address. The table is searched for all locations at which the system address may reside and then the translation from virtual to system is carried on in reverse in order to complete the reverse translation. See the related U.S. Pat. No. 4,551,797, Ser. No. 528,091, filed Aug. 30, 1983, APPARATUS FOR REVERSE TRANSLATION invented by Gene Myron Amdahl, Donald Laverne Hanson, Ronald Karl Kreuzenstein, Gwynne Lynn Roshon-Larsen and Gary Arthur Woffinden, filed contemporaneously herewith and owned by a common assignee.
The search of the data table storage unit can be a time consuming search when all locations in the data table must be examined to determine whether a copy of the system address undergoing reverse translation may reside.